﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MyDFSGetPath
{
    class Program
    {
        static int mapXlen, mapYlen,endPointX,endPointY,min;
        static void Main(string[] args)
        {
            min = 9999;
            endPointX = 0;endPointY = 0;
            Console.WriteLine("输入迷宫的横坐标长度，不能为负数也不能大于50：");
            mapXlen = int.Parse(Console.ReadLine().ToString());
            if (mapXlen < 0 || mapXlen > 50)
            {  Console.WriteLine("输入的数值超过范围,使用默认数值10");mapXlen=10;}
            Console.WriteLine("输入迷宫的纵坐标长度，不能为负数也不能大于50：");
            mapYlen = int.Parse(Console.ReadLine().ToString());
            if (mapYlen < 0 || mapYlen > 50)
            { Console.WriteLine("输入的数值超过范围,使用默认数值10"); mapYlen=10; }
            int[,] map = new int[mapXlen, mapYlen];            
            map[0, 0] = 2;//设置起点
            CreatePoint(ref map);//生成随机迷宫
            PrintMap(map);//将当前的随机迷宫打印出来
            //定义一个数组保存走过的点
            int[,] result = new int[mapXlen, mapYlen];
            result[0, 0] = 1;//设置起点为走过，避免重复走起点
            //dfs(0, 0, 0, map, result);            
            note[] queue = new note[mapXlen * mapYlen];//创建广度搜索所用的队列数组
            int head=0, tail=0;//tail指向队列最后一位的下一位，所以获取最后一位的时候使用tail-1
            queue[tail] = new note();//这里需要注意，创建的类数组的每一项目前都是空的(null)，我们在使用时，需要先对其赋值，否则调用的时候会导致程序错误，提示对不存在的引用进行操作
            queue[tail].x = 0;
            queue[tail].y = 0;
            queue[tail].s = 0;
            tail++;
            int flag = 0;//标记寻路是否完成
            //广度优先搜索，使用队列进行计算，先将父节点入队，通过父节点来判断有哪些子节点，子节点全部列出后，将父节点出队，在将每一个子节点作为父节点，继续判断所有子节点
            while(head<tail)
            {
                int[,] next = {
                {0,1 },//右
                {1,0 },//下
                {0,-1 },//左
                {-1,0 }//上
            };
                int tx, ty;//下一步可能的坐标
                for (int k=0;k<4;k++)
                {
                    tx = queue[head].x + next[k, 0];
                    ty = queue[head].y + next[k, 1];
                    //如果越界了，进行下一个方向的尝试
                    if (tx < 0 || tx > (mapXlen - 1) || ty < 0 || ty > (mapYlen - 1))
                        continue;
                    //检查当前点是不是障碍物,以及没有被走过
                    if (map[tx, ty] != 1 && result[tx, ty] == 0)
                    {
                        result[tx, ty] = 1;
                        //向队列中插入
                        queue[tail] = new note();
                        queue[tail].x = tx;
                        queue[tail].y = ty;
                        queue[tail].f = head;
                        queue[tail].s = queue[head].s + 1;
                        tail++;
                    }
                    if(tx==endPointX&&ty==endPointY)
                    {
                        flag = 1;
                        //这里已经到达终点，尝试输出路径，通过当前节点的父节点属性，就能够获取到父节点的坐标
                        //当前节点的下一个点就是终点，我们不用处理，当前点为head指向的节点
                        //这里我们克隆一个迷宫地图
                        int[,] res = (int[,])map.Clone();
                        int point=head;
                       while(point>0)
                        {
                            res[queue[point].x, queue[point].y] = 4;//将当前点的坐标在结果数组中标记为4，显示为走过的路径
                            point = queue[point].f;//将当前点的父节点序号赋值给point，当父节点等于0时，结束循环
                        }
                        PrintMap(res);
                        break;
                    }
                }
                if (flag == 1)
                    break;
                head++;
            }
            Console.WriteLine("使用广度优先搜索算法进行寻路，一共需要{0}步到达终点", queue[tail - 1].s);

        }
        /// <summary>
        /// 随机生成障碍点，随机生成一个终点
        /// </summary>
        static void CreatePoint(ref int [,] Map)
        {
            int wallNum;
            //设置障碍物的数量等于横坐标和纵坐标中较小的那一个
            wallNum =mapXlen<= mapYlen ? mapXlen : mapYlen;
            //将wallNum减去1，避免生成的障碍物导致没有路可以走
            wallNum--;
            //定义一个生成随机数的对象
            Random rd = new Random();
            //随机生成终点的横坐标和纵坐标
            //横纵坐标不能都为0，因为这个是起点坐标
            while (endPointX==0&&endPointY==0)
            {
               endPointX = rd.Next(mapXlen);//生成的横坐标随机数小于横坐标最大值
               endPointY = rd.Next(mapYlen);//生成的纵坐标随机数小于纵坐标最大值
            }
            //设置终点
            Map[endPointX, endPointY] = 3;
            //生成随机障碍,障碍不能放在起点和终点
            for(int i=0;i<wallNum;i++)
            {
                int zX = 0, zY = 0;
                   while((zX==0&&zY==0)||(zX==endPointX&&zY==endPointY))
                {
                    zX = rd.Next(mapXlen);
                    zY = rd.Next(mapYlen);                    
                }
                //如果当前随机的障碍已经存在了，则继续生成
                if (Map[zX, zY] == 1) { i--; }
                else { Map[zX, zY] = 1; }//如果当前随机点没有设置障碍，则进行设置
            }
            Console.WriteLine("障碍点和终点生成结束");
        }
        /// <summary>
        /// 打印迷宫地图
        /// </summary>
        /// <param name="Map"></param>
        static void PrintMap(int[,] Map)
        {
            Console.WriteLine();
            for (int x=0;x<mapXlen;x++)
            {
                for(int y=0;y<mapYlen;y++)
                {
                    int p = Map[x, y];
                    switch(p)
                    {
                        case 0://可以走的路
                            Console.Write("■");
                            break;
                        case 1://障碍物不能通过
                            Console.Write("▓");
                            break;
                        case 2://起点
                            Console.Write("●");
                            break;
                        case 3://终点
                            Console.Write("▲");
                            break;
                        case 4://走过的路径                            
                                Console.Write("Θ");
                            break;
                    }
                }
                Console.WriteLine();
            }
            Console.WriteLine("***********************迷宫地图打印完毕****************************");
        }

        /// <summary>
        /// Deep－First－Search
        /// 使用深度优先查询算法，进行迷宫路径搜索
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <param name="step"></param>
        /// <param name="Map"></param>
        static void dfs(int x,int y,int step,int[,] Map,int [,] Result)
        {
            //实际这里的右，下，左，上的顺序和打印出来的方向是不同的，因为默认x为纵坐标，y为横坐标了，但是不影响计算结果。多维数组的横纵坐标应该y为纵坐标
            int[,] next = {
                {0,1 },//右
                {1,0 },//下
                {0,-1 },//左
                {-1,0 }//上
            };
            int tx, ty;//下一步可能的坐标
            //是否到了终点
            if (x==endPointX&&y==endPointY)
            {
                if (step < min)
                { min = step;
                    //这里我们简化输出，只用当计算出的步数小于之前的最小步数，我们才打印路径
                    //这里我们克隆一个迷宫地图
                    int[,] res = (int[,])Map.Clone();
                    for (int i = 0; i < mapXlen; i++)
                    {
                        for (int j = 0; j < mapYlen; j++)
                        {
                            //如果是走过的路线
                            if (Result[i, j] == 1)
                            {
                                //如果是终点，则不进行修改
                                if (i == endPointX && j == endPointY)
                                    continue;
                                //如果是起点也不进行修改
                                if (i == 0 && j == 0)
                                    continue;
                                //否则标记为走过的线路
                                res[i, j] = 4;
                                //Result[i, j] = 0;
                            }
                        }
                    }
                    PrintMap(res);//打印结果  
                }                    
                //这里应该输出结果
                Console.WriteLine("*******本次迷宫寻路完成，一共走了{0}步*******",step);  
                return;
            }
            //每个点能够进行4个方向的尝试
            for(int k=0;k<4;k++)
            {
                tx = x + next[k, 0];
                ty = y + next[k, 1];
                //如果越界了，进行下一个方向的尝试
                if (tx < 0 || tx > (mapXlen - 1) || ty < 0 || ty > (mapYlen - 1))
                    continue;
                //检查当前点是不是障碍物,以及没有被走过
                if(Map[tx,ty]!=1&&Result[tx, ty]==0)
                {
                    //将该点设置为走过
                    Result[tx, ty] = 1;
                    dfs(tx, ty, step + 1, Map,Result);
                    Result[tx, ty] = 0;
                }
            }
            return;
        }



    }
    public class note
    {
        public note()
        {
            x = 0;
            y = 0;
            f = 0;
            s = 0;
        }
        public int x;//横坐标
        public int y;//纵坐标
        public int f;//父亲在队列中的编号
        public int s;//步数
    }
}
